package tiruvury.InterviewPrep.DataStructures;

import java.util.LinkedList;
import java.util.Queue;

import tiruvury.InterviewPrep.HelperClasses.BiNode;
import tiruvury.InterviewPrep.HelperClasses.TreeNode;

public class BinaryTree
{
	TreeNode root = null;

	public void CreateBinaryTree(int maxLevels)
	{
		Queue<TreeNode> queue = new LinkedList<TreeNode>();

		if (root == null)
		{
			root = new TreeNode(GetRandNum(), null, null);
			queue.offer(root);
		}

		int nodeCount = 1;
		while (nodeCount < Math.pow(2, maxLevels) && !queue.isEmpty())
		{
			TreeNode queueNode = queue.poll();
			TreeNode leftNode = null;
			TreeNode rightNode = null;
			if (queueNode != null)
			{
				leftNode = new TreeNode(GetRandNum(), null, null);
				queueNode.left = leftNode;
				queue.offer(leftNode);
				nodeCount++;

				rightNode = new TreeNode(GetRandNum(), null, null);
				queueNode.right = rightNode;
				queue.offer(rightNode);
				nodeCount++;
			}
		}
	}

	public void PrintBinaryTree(int maxLevels)
	{
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);

		int spaces = (int) Math.pow(2, maxLevels - 1);
		for (int i = 0; i < maxLevels; i++)
		{
			System.out.print("Level " + (i + 1) + " Nodes: {" + String.format("%" + spaces + "s", ""));
			int j = 0;
			while (!queue.isEmpty())
			{
				TreeNode queueNode = queue.poll();
				System.out.print(queueNode.data

				+ String.format("%" + 2 * spaces + "s", ""));
				j++;

				if (queueNode.left != null)
				{
					queue.offer(queueNode.left);
				}

				if (queueNode.right != null)
				{
					queue.offer(queueNode.right);
				}

				if (j == Math.pow(2, i))
				{
					break;
				}
			}
			System.out.println("}");
			spaces = spaces / 2;
		}
	}

	void PrintLevelOrderTraversal(TreeNode node)
	{
		int level = 1;
		/*
		 * SYNTAXERROR: Queue is only an interface. It needs to be implemented
		 * as a LinkedList or a PriorityQueue
		 */
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		if (node != null)
		{
			queue.add(node);
		}

		System.out.println("Printing level " + level + " nodes");
		level++;
		int currLevelNodes = queue.size();
		while (queue.size() > 0)
		{
			node = queue.poll();
			System.out.println(node.data);
			currLevelNodes--;

			if (node.left != null)
			{
				queue.add(node.left);
			}

			if (node.right != null)
			{
				queue.add(node.right);
			}

			if (currLevelNodes == 0 && queue.size() > 0)
			{
				System.out.println("Printing level " + level + " nodes");
				level++;
				currLevelNodes = queue.size();
			}
		}

	}

	/**
	 * Gayle 17.13
	 * DO COMPLEXITY ANALYSIS
	 * ALSO REVIEW
	 */
	BiNode ConvertBSTToDll(BiNode node, BiNode parent)
	{
		if (node == null)
		{
			return null;
		}

		BiNode returnNode = node;
		BiNode left = ConvertBSTToDll(node.node1, node);
		BiNode curr = node;
		BiNode right = ConvertBSTToDll(node.node2, node);

		if (parent != null)
		{
			if (curr.data <= parent.data)
			{
				// You're in the left subtree. Find the right-most child from
				// the current node.
				// That will become the prev BiNode for the parent in the DLL.
				while (curr.node2 != null)
				{
					returnNode = curr.node2;
					curr = curr.node2;
				}
			}
			else
			{
				// Right Subtree
				// Find the leftmost child from the current node which will
				// become the next BiNode for
				// the parent in the DLL
				while (curr.node1 != null)
				{
					returnNode = curr.node1;
					curr = curr.node1;
				}
			}
		}

		curr.node1 = left;
		curr.node2 = right;

		return returnNode;
	}

	private int GetRandNum()
	{
		return (int) (Math.random() * 100);
	}
}
